#include "GraphAlgo.h"

#include <iostream>

template <class Graph>
bool CheckSorting(const Graph &graph, const std::vector <int> &top_result)
{
    if (top_result.size() != graph.size())
        return false;
    for (size_t i = 0; i < graph.size(); i++)
    {
        bool is_top_sort = 1;
        graph.foreach_neighbour(i, [&top_result, &is_top_sort, &i] (int node)
                                   {
                                        for (size_t j = 0; j < top_result.size() && top_result[j] != i; j++)
                                            if (top_result[j] == node)
                                                is_top_sort = 1;
                                   });
        if (!is_top_sort)
            return false;
    }
    return true;
}

void TestTopSort()
{
    std::vector < std::vector <int> > graph;
    std::vector <int> top_sorted_vertices;
    ListGraph list_graph;
    graph = {{1, 2}, {2}, {}};
    list_graph.construct_by_list(graph);
    top_sorted_vertices = TopologicalSorting(list_graph);
    if (!CheckSorting(list_graph, top_sorted_vertices))
        throw std::logic_error("TestTopSort: wrong top sorted result");

    graph = {{4}, {0, 2, 3, 4}, {3, 4}, {4}, {}};
    list_graph.construct_by_list(graph);
    top_sorted_vertices = TopologicalSorting(list_graph);
    if (!CheckSorting(list_graph, top_sorted_vertices))
        throw std::logic_error("TestTopSort: wrong top sorted result");

    graph.resize(100);
    for (size_t i = 0; i < 99; i++)
    {
        graph[i].resize(1);
        graph[i][0] = i + 1;
    }
    list_graph.construct_by_list(graph);
    top_sorted_vertices = TopologicalSorting(list_graph);
    if (!CheckSorting(list_graph, top_sorted_vertices))
        throw std::logic_error("TestTopSort: wrong top sorted result");

    graph.resize(100);
    for (size_t i = 0; i < 99; i++)
        graph[i].resize(0);
    graph[50].resize(99);
    for (size_t i = 0; i < 99; i++)
        if (i != 50)
            graph[50].push_back(i);
    list_graph.construct_by_list(graph);
    top_sorted_vertices = TopologicalSorting(list_graph);
    if (!CheckSorting(list_graph, top_sorted_vertices))
        throw std::logic_error("TestTopSort: wrong top sorted result");
}

void TestGraphAlgo()
{
    TestTopSort();
}
